﻿ 

namespace Common.Algorithm.Core;

/// <summary>
/// 
/// </summary>
public class KruskalService
{
    private List<GraphEdge> _treeEdges = new List<GraphEdge>();

    public IList<GraphEdge> RunAlgm(IEnumerable<GraphEdge> edges)
    {
        edges = edges
            .Where(e => e.weight != 0)
            .OrderBy(e => e.weight);
         
        List<GraphEdge> treeEdges = new List<GraphEdge>();
        List<HashSet<int>> treeSets = new List<HashSet<int>>();//并查集采用hashset结构构造
        edges.Select(e => e.stVertexId).Distinct().ToList()
            .ForEach(id => treeSets.Add(new HashSet<int>() { id }));
         
        foreach (var edge in edges)
        {
            if (treeSets.Count() == 1) break;
            int stIndex = edge.stVertexId;
            int edIndex = edge.edVertexId;

            //边的两侧是否同树
            bool isInSameTree = treeSets.Any(t => t.Contains(stIndex) && t.Contains(edIndex));
            //当前边集合T是否有该边 
            bool isAdded = treeEdges.Contains(edge);
            //综合判断
            bool canAdd = !isInSameTree && !isAdded;

            if (canAdd)
            {
                treeEdges.Add(edge);//add

                var stTree = treeSets.Where(t => t.Contains(stIndex)).First();
                var edTree = treeSets.Where(t => t.Contains(edIndex)).First();

                stTree.UnionWith(edTree);
                treeSets.Remove(edTree);
            }
        }
        _treeEdges = treeEdges;
        return treeEdges;

    }

    public IList<TreeNode> GetTreeEntity()
    {
        List<TreeNode> treeNodes = new List<TreeNode>();
        List<GraphEdge> treeEdges = _treeEdges;

        foreach (var group in treeEdges.GroupBy(t => t.stVertexId))
        {
            TreeNode node = new TreeNode();
            node.id = group.First().id;
            node.childIds.AddRange(group.Select(g => g.edVertexId));
            treeNodes.Add(node);
        }

        return treeNodes;
    }

    public struct TreeNode
    {
        public TreeNode()
        {
            this.id = 0;
            this.childIds = new List<int>();
        }

        public int id { get; set; }
        public List<int> childIds { get; set; }
    } 
}
